package goleetcode

import "duan.com/leetcode/utils"

func buildTree2(inorder []int, postorder []int) *utils.TreeNode {
	idxMap := map[int]int{}
	for i, v := range inorder {
		idxMap[v] = i
	}
	var build func(int, int) *utils.TreeNode
	build = func(inorderLeft, inorderRight int) *utils.TreeNode {
		if inorderLeft > inorderRight {
			return nil
		}
		val := postorder[len(postorder) - 1]
		postorder = postorder[:len(postorder) - 1]
		root := &utils.TreeNode{Val: val}

		inorderRootIndex := idxMap[val]
		root.Right = build(inorderRootIndex + 1, inorderRight)
		root.Left = build(inorderLeft, inorderRootIndex - 1)
		return root
	}
	return build(0, len(inorder) - 1)
}